package code;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class Zigzag {
	 public static class TreeNode {
		      int val;
		      TreeNode left;
		      TreeNode right;
		      TreeNode(int x) { val = x; }
		  }
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> list=new ArrayList<List<Integer>>();
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		
		//��¼�������ڵĲ���
		Map<TreeNode,Integer> map=new HashMap<TreeNode,Integer>();
		
		if(root==null)	return list;
		queue.add(root);
		int cnt=0;
		int level=0;
		map.put(root, 1);
		//root�ǵ�һ��
		while(!queue.isEmpty()){
			TreeNode head=queue.poll();
			cnt=map.get(head);
			System.out.println(head.val);
			if(level<cnt){
				list.add(new ArrayList<Integer>());
				level=cnt;
			}
			if(level%2==1){
				list.get(level-1).add(head.val);
			}
			else{
				list.get(level-1).add(0, head.val);
			}
			if(head.left!=null){
				queue.add(head.left);
				map.put(head.left, cnt+1);
			}
			if(head.right!=null){
				queue.add(head.right);
				map.put(head.right, cnt+1);
			}
		}
		
        return list;
    }
	public static void main(String[] args){
		TreeNode node1=new TreeNode(1);
		TreeNode node2=new TreeNode(2);
		TreeNode node3=new TreeNode(3);
		TreeNode node4=new TreeNode(4);
		TreeNode node5=new TreeNode(5);
		
		node1.left=node2;
		node2.left=node4;
		node3.right=node5;
		node1.right=node3;
		
		Zigzag zz=new Zigzag();
		List<List<Integer>> list=zz.zigzagLevelOrder(node1);
		for(int i=0;i<list.size();i++){
			System.out.println("------ "+i+"-----------");
			for(int j=0;j<list.get(i).size();j++)
				System.out.println(list.get(i).get(j)+"   ");
		}
	}
}
